#include <iostream>
#include <fstream>
#include "Adaptive.h"

using namespace std;

void Adaptive::crawl(int cost_limit){
        setCostLimit(cost_limit);
		nodeRecall.Add(TFltPr(0,0));
		edgeRecall.Add(TFltPr(0,0));
		int below_threshold = 0;
		int n_below_threshold = 0;
		int totalCost = 0;
		double marginal_cost,marginal_recall,efficiency;
		TFltPr prev_recall, recall;
		network->disableCache();
		printf("Crawling using teleport...\n");
		do{
			totalCost = network->getTotalCost();
			if(telNextStep() == -1) //next step failed, can't find new node
				continue;
			totalCost = network->getTotalCost();
			
			if(totalCost < 0.1*cost_limit)
				continue;		
			prev_recall = nodeRecall[nodeRecall.Len()-2];
			recall = nodeRecall[nodeRecall.Len()-1];
			marginal_cost = recall.Val1 - prev_recall.Val1;
			marginal_recall = recall.Val2 - prev_recall.Val2;
			if(marginal_cost !=0){
				efficiency = marginal_recall/marginal_cost;
				if(efficiency < NODE_EFF_THRESHOLD){
					n_below_threshold++;
					if(n_below_threshold > MAX_ATTEMPTS/2)
						printf("Node Eff below threshold: %d, Value %f\n",n_below_threshold,efficiency);
				}
				else
					n_below_threshold = 0;
			}
			
			prev_recall = edgeRecall[edgeRecall.Len()-2];
			recall = edgeRecall[edgeRecall.Len()-1];
			marginal_cost = recall.Val1 - prev_recall.Val1;
			marginal_recall = recall.Val2 - prev_recall.Val2;
			if(marginal_cost !=0){
				efficiency = marginal_recall/marginal_cost;
				if(efficiency < EDGE_EFF_THRESHOLD){
					below_threshold++;
					if(below_threshold > MAX_ATTEMPTS/2)
						printf("Edge Eff below threshold: %d, Value %f\n",below_threshold,efficiency);
				}
				else
					below_threshold = 0;
			}
		}while(below_threshold < MAX_ATTEMPTS && n_below_threshold < MAX_ATTEMPTS && totalCost < 0.3*cost_limit);
		printf("Switched from teleport to optimized greedy...\n");
		totalCost = network->getTotalCost();
		printf("Total Cost: %d\n",totalCost);
		printf("Node Recall: %d\n",(int)nodeRecall[nodeRecall.Len()-1].Val2);
		printf("Edge Recall: %d\n",(int)edgeRecall[edgeRecall.Len()-1].Val2);
		
	  	ofstream myfile;
		myfile.open ("log.txt");
  		myfile << "Total Cost: "<<totalCost<<endl;
		myfile << "Node Recall: "<<(int)(nodeRecall[nodeRecall.Len()-1].Val2) << endl;
		myfile << "Edge Recall: "<< (int)(edgeRecall[edgeRecall.Len()-1].Val2) << endl;
  		myfile.close();

		//save progress	
		{
			TFOut FOut1("/lfs/1/tmp/saint/twitter/adaptive_n.bin");   		
			nodeRecall.Save(FOut1);
			TFOut FOut2("/lfs/1/tmp/saint/twitter/adaptive_e.bin");   		
			edgeRecall.Save(FOut2);
		}

		//switch to optimized greedy (greedy4)
		//first buid the priority queue
		printf("Building priority queue for optimized greedy\n");
		//crawled nodes are in tel_visited and seen nodes are in Discover
		for(int i=0; i < tel_visited.Len();i++){
			int NID = tel_visited.GetKey(i);
			visit[NID] =  TIntQu(0,0, 0, 0);//mark as visited (fully crawled)
		}
		printf("Mark crawled nodes from teleport as crawled.\n");
		TIntV NIDs;
		network->Discover->GetNIdV(NIDs);
		for(int i=0; i < NIDs.Len() && network->getTotalCost() < cost_limit ;i++){
			int NID = NIDs[i];
			int Lenb4 = NIDs.Len();
			updateDiscoveredNode(NID);
			if(NIDs.Len()!=Lenb4){
				printf("Length Changed!");
				return;
			}
		    	TIntPr p = network->evaluate();
			totalCost = network->getTotalCost();
			if(totalCost % 10000 < 5) 
				printf("Total Cost: %d, %d nodes processed.\n",totalCost,i+1);
			
			nodeRecall.Add(TFltPr(totalCost, double(p.Val1)));
		    edgeRecall.Add(TFltPr(totalCost, double(p.Val2)));
		}


		//save progress	
		{
			TFOut FOut1("/lfs/1/tmp/saint/twitter/adaptive_n.bin");   		
			nodeRecall.Save(FOut1);
			TFOut FOut2("/lfs/1/tmp/saint/twitter/adaptive_e.bin");   		
			edgeRecall.Save(FOut2);
		}

		//crawl using greedy4
		network->enableCache();
		printf("Crawling using optimized greedy...\n");		

        while(network->getTotalCost() < cost_limit)nextStep(); 
		
		//save progress	
		{
			TFOut FOut1("/lfs/1/tmp/saint/twitter/adaptive_n.bin");   		
			nodeRecall.Save(FOut1);
			TFOut FOut2("/lfs/1/tmp/saint/twitter/adaptive_e.bin");   		
			edgeRecall.Save(FOut2);
		}
}


int Adaptive::telNextStep(){
    int nid = telNodeToExplore();
    if (nid == -1)
      return -1;
    network->getAllFollowers(nid);
    network->getAllFollowees(nid);
    TIntPr p = network->evaluate();
    int totalCost = network->getTotalCost();
    if(totalCost % 1000 < 5) 
		printf("Total Cost: %d\n",totalCost);
    //if(totalCost % 1000 == 0){
    nodeRecall.Add(TFltPr(totalCost, double(p.Val1)));
    edgeRecall.Add(TFltPr(totalCost, double(p.Val2)));
    //}
	return 0;
}

int Adaptive::telNodeToExplore() {
      int nid;
      while (1) {
	nid = network->getTeleportNode();
	if (nid == -1)
	  return -1;
	if (!tel_visited.IsKey(nid))
	  break;
      }
      tel_visited.AddKey(nid);
      return nid;
}


void Adaptive::nextStep() {
    int nid = nodeToExplore();
    TVec<TInt> rec;
    if (visit[nid].Val1 > visit[nid].Val2) {
      rec = network->getFollowers(nid, visit[nid].Val3);
      visit[nid].Val1 -= rec.Len();
      visit[nid].Val3 += rec.Len();
      if (visit[nid].Val1 != 0) {
	q.push(TIntPr(visit[nid].Val1, nid));
      }
    } else {
      rec = network->getFollowees(nid, visit[nid].Val4);
      visit[nid].Val2 -= rec.Len();
      visit[nid].Val4 += rec.Len();
      if (visit[nid].Val2 != 0) {
	q.push(TIntPr(visit[nid].Val2, nid));
      }
    }
    for(TVec<TInt>::TIter i = rec.BegI(); i != rec.EndI(); i++)
        updateDiscoveredNode(i->Val);
    TIntPr p = network->evaluate();
    int totalCost = network->getTotalCost();
    //if(totalCost % 1000 == 0){
    nodeRecall.Add(TFltPr(totalCost, double(p.Val1)));
    edgeRecall.Add(TFltPr(totalCost, double(p.Val2)));
    //}
}

int Adaptive::nodeToExplore() {
  int nid;
  if (!q.empty()) {
    nid = q.top().Val2;
    q.pop();
  } else {
    nid = network->getTeleportNode();
    updateDiscoveredNode(nid);
  }
  return nid;
}

void Adaptive::updateDiscoveredNode(int discoveredNode) {
  if (visit.find(discoveredNode) == visit.end()) {
    TIntPr deg;
    deg.Val1 = network->getFollowers(discoveredNode).Len();
    deg.Val2 = network->getFollowees(discoveredNode).Len();
    if (deg.Val1 >= C || deg.Val2 >= C)
      deg = network->getDegree(discoveredNode);
    q.push(TIntPr(deg.Val1, discoveredNode));
    q.push(TIntPr(deg.Val2, discoveredNode));
    visit[discoveredNode] = TIntQu(deg.Val1, deg.Val2, 0, 0);
  }
}

